package com.mj.listen2._08_动态规划;

/**
 * 假设有 25 分、20 分、5 分、1 分的硬币，
 * 现要找给客户 41 分的零钱，如何办到硬币个数最少？
 */
public class CoinChange {
    public static void main(String[] args) {
        System.out.println(coins(1, new int[]{1, 5, 20, 25}));
    }

    /**
     * 找零钱 - 通用实现终版
     */
    static int coins(int n, int[] faces) {
        if (n < 1 || faces == null || faces.length == 0) return -1;
        // 数组含义：凑到 n 分需要的最少硬币个数。dp[5] = 1：凑到 5 分需要的最少硬币个数 1 枚
        int[] dp = new int[n + 1];
        // dp[n] = min { dp[n - 25], dp[n - 20], dp[n - 5], dp[n - 1] } + 1;
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                // 假如给我的面值是20, 要凑的是15, 则跳过此轮循环
                if (i < face) continue;// 如果给我的面值比我要凑的面值还大, 跳过此轮循环
                int v = dp[i - face];
                if (v < 0) continue;
                min = Math.min(min, v);
            }

            if (min == Integer.MAX_VALUE) {
                dp[i] = -1;
            } else {
                dp[i] = min + 1;
            }

        }
        return dp[n];
    }

    /**
     * 找零钱 - 通用实现
     */
    static int coins5(int n, int[] faces) {
        if (n < 1 || faces == null || faces.length == 0) return -1;
        // 数组含义：凑到 n 分需要的最少硬币个数。dp[5] = 1：凑到 5 分需要的最少硬币个数 1 枚
        int[] dp = new int[n + 1];
        // dp[n] = min { dp[n - 25], dp[n - 20], dp[n - 5], dp[n - 1] } + 1;
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                // 假如给我的面值是20, 要凑的是15, 则跳过此轮循环
                if (i < face) continue;// 如果给我的面值比我要凑的面值还大, 跳过此轮循环
                min = Math.min(min, dp[i - face]);
            }
            dp[i] = min + 1;
        }
        return dp[n];
    }

    /**
     * 递推(自底向上)
     */
    static int coins4(int n) {
        if (n < 1) return -1;
        // 数组含义：凑到 n 分需要的最少硬币个数。dp[5] = 1：凑到 5 分需要的最少硬币个数 1 枚
        int[] dp = new int[n + 1];
        // 自底向上的递推
        for (int i = 1; i <= n; i++) {
            // dp[n] = min { dp[n - 25], dp[n - 20], dp[n - 5], dp[n - 1] } + 1;
            int min = dp[i - 1];
            if (i >= 5) min = Math.min(min, dp[i - 5]);
            if (i >= 20) min = Math.min(min, dp[i - 20]);
            if (i >= 25) min = Math.min(min, dp[i - 25]);
            dp[i] = min + 1;
        }
        return dp[n];
    }

    /**
     * 递推(自底向上)
     */
    static int coins3(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        // 自底向上的递推
        for (int i = 1; i <= n; i++) {
            // dp[n] = min { dp[n - 25], dp[n - 20], dp[n - 5], dp[n - 1] } + 1;
            int min = Integer.MAX_VALUE;
            if (i >= 1) min = Math.min(min, dp[i - 1]);
            if (i >= 5) min = Math.min(min, dp[i - 5]);
            if (i >= 20) min = Math.min(min, dp[i - 20]);
            if (i >= 25) min = Math.min(min, dp[i - 25]);
            dp[i] = min + 1;
        }
        return dp[n];
    }

    /**
     * @return 凑到 n 分需要的最少硬币个数
     */
    static int coins2(int n) {
        if (n < 1) return -1;
        // 数组含义：凑到 n 分需要的最少硬币个数。dp[5] = 1：凑到 5 分需要的最少硬币个数 1 枚
        int[] dp = new int[n + 1];
        int[] faces = {1, 5, 20, 25}; // 给定的面值数组
        // 初始化
        for (int face : faces) {
            // 如果我要凑的钱是20元, 那么我肯定用不到25元面值
            if (n < face) {
                break;
            }
            // 初始化
            dp[face] = 1;
        }

        return coins2(n, dp);
    }

    private static int coins2(int n, int[] dp) {
        if (n < 1) return Integer.MAX_VALUE;
        if (dp[n] == 0) {
            // 还没缓存过
            int min1 = Math.min(coins1(n - 25), coins1(n - 20));
            int min2 = Math.min(coins1(n - 5), coins1(n - 1));
            // 缓存
            dp[n] = Math.min(min1, min2) + 1;
        }
        return dp[n];
    }

    /**
     * @return 凑到 n 分需要的最少硬币个数
     */
    static int coins1(int n) {
        // 递归基
        if (n < 1) return Integer.MAX_VALUE;
        if (n == 1 || n == 5 || n == 20 || n == 25) return 1; // 边界情况
        // 求出四种取法的最小值
        // dp(n) = min { dp(n - 25), dp(n - 20), dp(n - 5), dp(n - 1) } + 1
        int min1 = Math.min(coins1(n - 25), coins1(n - 20));
        int min2 = Math.min(coins1(n - 5), coins1(n - 1));
        return Math.min(min1, min2) + 1;
    }
}